package org.labuladong.暴力搜索算法.回溯算法;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-17:29
 * @Description:
 * @version: 1.0
 */
public class LCR_085_生成匹配的括号 {

	public List<String> generateParenthesis(int n) {
		List<String> res = new ArrayList<>();
		backtrack(res, "", 0, 0, n);
		return res;
	}

	private void backtrack(List<String> res, String current, int open, int close, int max) {
		// 如果current的长度等于2 * n，说明找到了一个有效的组合
		if (current.length() == 2 * max) {
			res.add(current);
			return;
		}

		// 如果current中open小于max，可以添加一个左括号
		if (open < max) {
			backtrack(res, current + "(", open + 1, close, max);
		}

		// 如果current中close小于open，可以添加一个右括号
		if (close < open) {
			backtrack(res, current + ")", open, close + 1, max);
		}
	}

}
